import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;


public class Matrix 
{
	private double [][] data;
        public int nbLine;
        public int nbColumn;
	
	public Matrix(int line, int column)
	{
		this.data = new double[line][column];
                this.nbLine = line;
                this.nbColumn = column;
                
                for(int i = 0; i < line; i++)
                {
                    for(int j = 0; j < column; j++)
                    {
                        this.data[i][j] = 0.0;
                    }
                }
	}
        
        public Matrix(double [][] data)
        {
            this.data = data;
            this.nbLine = data.length;
            this.nbColumn = data[0].length;
        }
	
        public void randomize(double lowest, double highest)
        {
            for (int i = 0; i < this.nbLine; i++)
            {
                for (int j = 0; j < this.nbColumn; j++)
                {
                    this.data[i][j] = (Math.random() * (highest - lowest)) + lowest;
                }
            }
        }
        
	public void setUpperTriangular()
	{
                for (int i = 0; i < this.nbLine; i++)
                {
                    for (int j = 0; j < this.nbColumn; j++)
                    {
                        if (i > j)
                        {
                            this.data[i][j] = 0.0;
                        }
                    }
                }
	}
	
	public void setLowerTriangular()
	{
                for (int i = 0; i < this.nbLine; i++)
                {
                    for (int j = 0; j < this.nbColumn; j++)
                    {
                        if (j > i)
                        {
                            this.data[i][j] = 0.0;
                        }
                    }
                }
	}
	
	public String toString()
        {
		String res = "";
                
                for (int i = 0; i < this.nbLine; i++)
                {
                    for(int j = 0; j < this.nbColumn; j++)
                    {
                       res += String.format("%1$.2f", this.data[i][j]) + " ";
                    }
                    res += "\n";
                }

		return res;
	}
        
	public double getValue(int line, int column)
	{
		return this.data[line][column];
	}
        
	public void setValue(int line, int column, double value)
	{
		this.data[line][column] = value;
	}
        
	public double[][] getData()
	{
		return this.data;
	}
        
	public static Matrix copy(Matrix mat)
	{
		Matrix res = new Matrix(mat.nbLine,mat.nbColumn);
                             
                for (int i = 0; i < mat.nbLine; i++)
                {
                    System.arraycopy(mat.data[i], 0, res.data[i], 0, mat.nbColumn);
                }

		return res;
	}
        
        public static Matrix solveLowerTriangular(Matrix a, Matrix b)
	{
                Matrix x = new Matrix(a.nbLine, 1);
                
          	double prec = b.getValue(0, 0)/ a.getValue(0, 0);
                x.setValue(0, 0, prec);
                
		for (int i = 1; i < b.nbLine; i++)
                {
                    double sommePrec = a.getValue(i, 0) * x.getValue(0, 0);
                    
                    for (int j = 1; j < i; j++) {
                        double fractionCourante = a.getValue(i, j)* x.getValue(j, 0);
                        sommePrec = sommePrec + fractionCourante;
                    }
                    
                    double numPrec = b.getValue(i, 0) - sommePrec;
                    prec = numPrec / a.getValue(i, i);
                    
                    x.setValue(i, 0, prec);
                }
                
                return x;
	}
        
        
	public static Matrix solveUpperTriangular(Matrix a, Matrix b)
	{
		Matrix x = new Matrix(a.nbLine, 1);
                
          	double prec = b.getValue(b.nbLine - 1, 0)/ a.getValue(a.nbLine - 1, a.nbColumn - 1);
                x.setValue(x.nbLine - 1, 0, prec);
                
		for (int i = b.nbLine - 2; i >= 0; i--)
                {
                    double sommePrec = a.getValue(i, a.nbColumn - 1)* x.getValue(x.nbLine - 1, 0);
                    
                    for (int j = a.nbColumn - 2; j > i; j--)
                    {
                        double fractionCourante = a.getValue(i, j)* x.getValue(j, 0);
                        sommePrec = sommePrec + fractionCourante;
                    }
                    
                    double numPrec = b.getValue(i, 0) - sommePrec;
                    prec = numPrec / a.getValue(i, i);
                    
                    x.setValue(i, 0, prec);
                }
                
                return x;
	}
        
        public static Matrix getU(Matrix m) {
            return LUDecomposition(m)[0];
        }
        
        public static Matrix getL(Matrix m) {
            return LUDecomposition(m)[1];
        }

	public static Matrix[] LUDecomposition(Matrix m)
	{
		Matrix l = new Matrix(m.nbLine, m.nbColumn);
                Matrix u = Matrix.copy(m);
                
                for (int i = 0; i < m.nbLine; i++)
		{
			l.setValue(i, i, 1.0);
		}
                
                for (int j = 0; j < u.nbColumn; j++)
		{
			for (int i = j + 1; i < l.nbLine; i++)
			{
                            if (u.getValue(i, j) != 0.0)
                            {

				double coeff = u.getValue(i, j) / u.getValue(j, j);
				l.setValue(i, j, coeff);
                                
                                for (int k = j; k < u.nbColumn; k++) 
                                {
                                    double fReduced = (u.getValue(i, k)) - (coeff * u.getValue(j, k));                                    
                                    u.setValue(i, k, fReduced);
                                }
                            }
                        }
		}
                
                Matrix[] res = {l, u};
                
		return res;
	}
        
        public static Matrix gaussWithoutPivoting(Matrix m)
	{
		Matrix res = Matrix.copy(m);
                
		for (int j = 0; j < res.nbColumn; j++)
                {       
                    for (int i = j + 1; i < res.nbLine; i++)
                    {
                        if (res.getValue(i, j) != 0)
                        {
                            double coeff = res.getValue(i, j) / res.getValue(j, j);

                            for (int k = j; k < res.nbColumn; k++) 
                            {
                                double fReduced = (res.getValue(i, k)) - (coeff * res.getValue(j, k));                                    
                                res.setValue(i, k, fReduced);
                            }
                        }
                    }
		}
                
                return res;
	}
                
   /*public static Matrix importCSV(String nomFichier) throws FileNotFoundException, IOException
   {
       ArrayList<double[]> mat = new ArrayList<>();
       File file = new File(nomFichier);
       BufferedReader bufRdr = new BufferedReader(new FileReader(file));
       String line = "";
       
       while ((line = bufRdr.readLine()) != null)
       {
            String[] tokens = line.split(";");
            double[] fraArray = new double[tokens.length];
            
            for (int i = 0; i < tokens.length; i++)
            {
                fraArray[i] = Double.parseDouble(tokens[i]);
            }
            
            mat.add(fraArray);
       }
       
       double[][] data = new double[mat.size()][mat.get(0).length];
       for (int i = 0; i < mat.size(); i++)
       {
           for (int j = 0; j < mat.get(i).length; j++)
           {
               data[i][j] = mat.get(i)[j];
           }
       }
       
       Matrix res = new Matrix(data);
       
       return res;
   }
   
      public void exportCSV(String nomFichier) throws FileNotFoundException, IOException
   {
       FileWriter writer = new FileWriter(nomFichier+".csv");
       for(int i = 0; i<this.nbLine; i++)
       {
           for(int j = 0; j<this.nbColumn; j++)
           {
               writer.write(this.data[i][j]+";");
           }
           
           writer.write("\n");
       }
       
       writer.close();   
   }*/
      
      public Matrix multiply(Matrix b)
      {
          Matrix res = null;
          
          //Condition sur les dimensions
          if(this.nbColumn == b.nbLine)
          {
                res = new Matrix(this.nbLine,b.nbColumn);
                double temp = 0.0;
                int a_col = 0;
                
                for(int a_lines = 0; a_lines< this.nbLine; a_lines++)
                {
                    for(int b_col = 0; b_col < b.nbColumn; b_col++)
                    {
                        for(a_col = 0; a_col < this.nbColumn; a_col++)
                        {
                            temp += this.data[a_lines][a_col]*b.data[a_col][b_col];
                        }  
                        res.data[a_lines][b_col] = temp;
                        temp = 0.0;
                    }
                }
          }
          return res;
      }
      
       public Matrix choleskyDecomposition()
       {
           Matrix res = new Matrix(this.nbLine,this.nbColumn);
           int col = 0;
           int lines = 0;
           
           //Stocke la Somme de k = 1 à (colonne - 1) de (res[colonne][k])^2
           double somme[] = new double[this.nbLine]; 
           //Stocke la Somme de k = 1 à (colonne - 1) de (res[ligne][k])*(res[colonne][k])
           double mult[] = new double[this.nbLine];
                   
            for(col = 0; col< this.nbColumn; col++)
            {
                res.data[col][col] = Math.sqrt(this.data[col][col] - somme[col]);
                
                for(lines = col+1; lines < this.nbLine; lines++)
                {
                    res.data[lines][col] = (this.data[lines][col]-mult[lines])/res.data[col][col];
                    somme[lines] += res.data[lines][col]*res.data[lines][col];
                    mult[lines] += res.data[lines-1][col]*res.data[lines][col];
                }
            }
            
            return res;
       }
       
       public Matrix Jacobi(Matrix b, double Epsilon)
       {
           // Test si matrice strictement dominante ?
           Matrix VecteurX = new Matrix(this.nbLine,1);
           Matrix VecteurXPlus = new Matrix(this.nbLine,1);
           Matrix VecteurResidu = new Matrix(this.nbLine,1);
           Matrix VecteurResiduPlus = new Matrix(this.nbLine,1);
           for (double[] row: VecteurResidu.data)
           Arrays.fill(row, 0.1);
          
           double tempX = 0.0;
           double tempR = 0.0;
           double erreur = Double.MAX_VALUE;
           double normeResidu = 0.0;
           double normeB = 0.0;
           int iteration;

           for(iteration = 0; erreur > Epsilon && iteration <1000; iteration++)
           {
                for(int ligne = 0; ligne < this.nbLine; ligne++)
                {
                    for(int colonne = 0; colonne < this.nbColumn; colonne++)
                    {
                        if(ligne != colonne)
                        {
                             tempX += this.data[ligne][colonne]*VecteurX.data[colonne][0];
                             tempR += this.data[ligne][colonne]*(VecteurResidu.data[colonne][0]/this.data[ligne][ligne]);
                        }
                    }
                    
                    VecteurXPlus.data[ligne][0] = ((b.data[ligne][0]-tempX)/this.data[ligne][ligne]);
                    VecteurResiduPlus.data[ligne][0] = -tempR;
                    //Pareil ?
                    //VecteurX.data[ligne][0] = ((b.data[ligne][0]-tempX)/this.data[ligne][ligne]);
                    //VecteurResidu.data[ligne][0] = -tempR;
                    tempX = 0;
                    tempR = 0;
                }

                VecteurX.data = VecteurXPlus.data;
                VecteurResidu.data = VecteurResiduPlus.data;
                
                for(int i = 0; i<b.nbLine; i++)
                {
                    normeResidu += VecteurResidu.data[i][0]*VecteurResidu.data[i][0];
                    normeB += b.data[i][0]*b.data[i][0];           
                }
                
                erreur = Math.sqrt(normeResidu)/Math.sqrt(normeB);
                normeResidu = 0;
                normeB = 0;
                
                
                
                //Norme Infinie
                /*double maxR = Double.MIN_VALUE;
                double maxB = Double.MIN_VALUE;
                for(int i = 0; i<b.nbLine; i++)
                {
                   if(VecteurResidu.data[i][0] > maxR) 
                   maxR = VecteurResidu.data[i][0];
                   
                   if(b.data[i][0] > maxB) 
                   maxB = b.data[i][0];
                }
                erreur = maxR / maxB;*/


           }
            
            System.out.println("Résultat après " + iteration + " itérations :\nErreur : "+erreur);
            return VecteurX;
       }
       
       public Matrix subtraction(Matrix b)
       {
           Matrix res = new Matrix(this.nbLine, this.nbColumn);
           if(this.nbColumn == b.nbColumn && this.nbLine == b.nbLine)
           {
               for(int lignes = 0; lignes < this.nbLine; lignes++)
               {
                   for(int colonnes = 0; colonnes < this.nbColumn; colonnes++)
                   {
                       res.data[lignes][colonnes] = this.data[lignes][colonnes] - b.data[lignes][colonnes];
                   }
               }
           }
           
           return res;
       }
       
       public Matrix gaussSeidel(Matrix b, double Epsilon)
       {
           //Vérifier que termes diagonaux non nuls
           Matrix VecteurX = new Matrix(this.nbLine,1);
           Matrix VecteurResidu;
           double normeResidu = 0.0;
           double normeB = 0.0;
           double erreur = Double.MAX_VALUE;

           double sommeA = 0;
           double sommeB = 0;
           int iteration = 1;
           
           //Nécessaire ?
           for (double[] row: VecteurX.data)
           Arrays.fill(row, 0.1);
           
           while(erreur > Epsilon && iteration < 500)
           {
                for(int lignes = 0; lignes < this.nbLine; lignes++)
                {
                    for(int colonnes = 1; colonnes < lignes-1; colonnes++)
                    {
                        sommeA += this.data[lignes][colonnes] * VecteurX.data[colonnes][0];
                    }
                    for(int colonnes = lignes+1; colonnes < this.nbColumn; colonnes++)
                    {
                        sommeB += this.data[lignes][colonnes] * VecteurX.data[colonnes][0];
                    }
                    
                    VecteurX.data[lignes][0] = (b.data[lignes][0] - sommeA - sommeB)/this.data[lignes][lignes];
                    sommeA = 0;
                    sommeB = 0;
                }

                VecteurResidu = b.subtraction(this.multiply(VecteurX));

                 for(int i = 0; i<b.nbLine; i++)
                     {
                         normeResidu += VecteurResidu.data[i][0]*VecteurResidu.data[i][0];
                         normeB += b.data[i][0]*b.data[i][0];           
                     }

                     erreur = Math.sqrt(normeResidu)/Math.sqrt(normeB);
                     normeResidu = 0;
                     normeB = 0;
                 iteration++;
            }
           
           return VecteurX;
       }
       
   public static Matrix importMTX(String nomFichier) throws FileNotFoundException, IOException
   {
       //ArrayList<double[]> mat = new ArrayList<>();
       File file = new File(nomFichier);
       BufferedReader bufRdr = new BufferedReader(new FileReader(file));
       String line = "";
       String[] type = null;

       if((line = bufRdr.readLine()).startsWith("%%MatrixMarket")) 
       {
           type = line.substring(line.indexOf("matrix")+7, line.length()).split("( )+");
       }
       line = bufRdr.readLine();
       String[] params = line.split(" ");
       Matrix res = new Matrix(Integer.parseInt(params[0]),Integer.parseInt(params[1]));

       if(res.nbColumn > 1)
       {
           if(type[0].equals("coordinate"))
           {   
               switch(type[2].charAt(1))
               {
                   //general
                   case 'e' :
                     while ((line = bufRdr.readLine()) != null)
                     {
                         String[] tokens = line.split("( )+");
                         res.data[Integer.parseInt(tokens[0])-1][Integer.parseInt(tokens[1])-1] = (Double.valueOf(tokens[2].trim())).doubleValue();
                     }
                   break;
                       
                   //symmetric    
                   case 'y' :
                     while ((line = bufRdr.readLine()) != null)
                     {
                         String[] tokens = line.split("( )+");
                         res.data[Integer.parseInt(tokens[0])-1][Integer.parseInt(tokens[1])-1] = (Double.valueOf(tokens[2].trim())).doubleValue();
                         res.data[Integer.parseInt(tokens[1])-1][Integer.parseInt(tokens[0])-1] = (Double.valueOf(tokens[2].trim())).doubleValue();
                     }
                   break;
                       
                   //skew-symmetric    
                   case 'k' :
                     while ((line = bufRdr.readLine()) != null)
                     {
                         String[] tokens = line.split("( )+");
                         res.data[Integer.parseInt(tokens[0])-1][Integer.parseInt(tokens[1])-1] = (Double.valueOf(tokens[2].trim())).doubleValue();
                         res.data[Integer.parseInt(tokens[1])-1][Integer.parseInt(tokens[0])-1] = -(Double.valueOf(tokens[2].trim())).doubleValue();
                     }
                   break;
               }
           }
           
           //Array format
           else
           {
               int l = 0;
               int c = 0;
               while ((line = bufRdr.readLine()) != null)
               {
                   res.data[l][c] = (Double.valueOf(line.trim())).doubleValue();
                   if(l == res.nbLine)
                   {
                       l = 0;
                       c++;
                   }
                   else
                   {
                      l++;   
                   }
               }
           }
       }
       
       //Une colonne
       else
       {
        int nligne = 0;

        while ((line = bufRdr.readLine()) != null)
            {
                 res.data[nligne][0] = (Double.valueOf(line.trim())).doubleValue();
                 nligne++;
            }  
       }
       
       bufRdr.close();

       return res;
   }
   
   public void exportMTX(String nomFichier, String type) throws FileNotFoundException, IOException
   {
       FileWriter writer = new FileWriter(nomFichier+".mtx");
       //Méthode pour trouver le type de la matrice ?
       writer.write("%%MatrixMarket matrix "+ type +"\n");
       //writer.write("%%Généré par man2013 : Antoine / Magalie / Etienne : "+commentaire+"\n");
       String res = "";
       int nbZero = 0;
       
       if(this.nbColumn > 1)
       {
            for(int i = 0; i<this.nbLine; i++)
            {
                for(int j = 0; j<this.nbColumn; j++)
                {
                    if(this.data[i][j] != 0)
                    {
                        res += (i+1) + " " + (j+1) + " " + this.data[i][j]+"\n";
                        nbZero++;
                    }
                }
            }
            
            writer.write(this.nbLine + " " + this.nbColumn + " " + nbZero+"\n");
       }
       
       else
       {
            for(int i = 0; i<this.nbLine; i++)
            {
               res += this.data[i][0]+"\n";
            }
            
            writer.write(this.nbLine + " " + this.nbColumn+"\n");
       }
       
       writer.write(res);
       
       writer.close();   
   }
   
   public static double getNorme(Matrix a)
   {
       double norme = 0.0;
       
       if(a.nbColumn == 1)
       {
       for(int i = 0; i<a.nbLine; i++)
       {
            norme += a.data[i][0]*a.data[i][0];           
       }

        norme = Math.sqrt(norme);
       }
       
       else{

           double temp = 0.0;
           double max = Double.MIN_VALUE;
           
           for(int i = 0; i<a.nbLine; i++)
           {
              for(int j = 0; j<a.nbColumn; j++)
              {
                 temp += Math.abs(a.data[i][j]);
              }
              
               if(temp > max)
               {
                   max = temp;
               }
               temp = 0.0;
           }
           
         norme = max;        
       }
       
       return norme;
   }
   
   public Matrix getTransposee()
   {
       Matrix res = new Matrix(this.nbColumn, this.nbLine);
       for(int i = 0; i< this.nbLine; i++)
       {
           for(int j = 0; j< this.nbColumn; j++)
           {
               res.data[j][i] = this.data[i][j];
           }
       }
       
       return res;
   }
   
   public String verifDiagonaleNonNulle()
   {
       String res = "";
       
       if(this.nbColumn != this.nbLine)
       {
           res = "La matrice A n'est pas carrée !";
       }
       
       else
       {
            for(int i = 0; i<this.nbLine; i++)
            {
                if(this.data[i][i] == 0)
                {
                    res = "Diagonale nulle en ("+i+"; "+i+")";
                }
            }
       }
       
       return res;
   }
              
}